The present invention relates to methods of encoding video sequences and in particular to a method of optimally setting the dimensions of the search window for a most efficient coding.
The invention is useful in digital video coders where it is necessary to evaluate the activity of a block of information in the frequency domain.
Because of the particular importance of the of the widely applied MPEG standard in treating digitized video sequences, to illustrate a practical implementation of the method of the invention, a description of the method implemented within an MPEG2 coding will be presented. Obviously, the method of the invention remains perfectly valid and advantageously applicable even in decoders based on different standards (other than the MPEG), as they are defined from time to time.
The MPEG (Moving Pictures Experts Group) standard defines a set of algorithms dedicated to the compression of sequences of digitized pictures. These techniques are based on the reduction of the temporal, spatial and statistical redundance of the information constituting the sequence.
Reduction of spatial and statistical redundance is achieved by compressing independently the single images, by means of discrete cosine transform (DCT), quantization and variable length Huffman coding.
The reduction of temporal redundance is obtained using the correlation that exist between successive pictures of a sequence. Approximately, it may be said that each image can be expressed, locally, as a translation of a previous and/or subsequent image of the sequence. To this end, the MPEG standard uses three kinds of pictures, indicated with I (Intra Coded Frame), P (Predicted Frame) and B (Bidirectionally Predicted Frame). The I pictures are coded in a fully independent mode; the P pictures are coded in respect to a preceding I or P picture in the sequence; the B pictures are coded in respect to two pictures, of I or P kind: the preceding one and the following one in the video sequence.
A typical sequence of pictures can be the following one: I B B P B B P B B I B . . . This is the order in which they will be viewed, but given that any P is coded in respect to the previous I or P, and any B in respect to the preceding and following I or P, it is necessary that the decoder receive the P pictures before the B pictures, and the I pictures before the P pictures. Therefore the order of transmission of the pictures will be I P B B P B B I B B . . .
Pictures are elaborated by the coder sequentially, in the indicated order, and subsequently sent to a decoder which decodes and reorders them, allowing their subsequent displaying. To codify a B picture it is necessary for the coder to keep in a dedicated memory buffer, called xe2x80x9cframe memoryxe2x80x9d, the I and P pictures, coded and thereafter decoded, to which a current B picture refers, thus requiring an appropriate memory capacity.
One of the most important functions in coding is motion estimation. Motion estimation is based on the following consideration: a set of pixels of a picture frame called current pixel set may be placed in a position of the subsequent and/or precedent picture obtained by rigid translation of the corresponding one to the current pixel set. Of course, these transpositions of objects may expose parts that were not visible before as well as changes of their shape (e.g. during a zooming, rotations and the like).
The family of algorithms suitable to identify and associate these portions of pictures is generally referred to as of xe2x80x9cmotion estimationxe2x80x9d. Such association of pixels is instrumental to calculate the relative coordinates between the current portion and the portion identified as the best predictor, and to calculate the portion of picture difference, so removing redundant temporal information, thus making more effective the subsequent processes of DCT compression, quantization and entropic coding.
Such a method finds a typical example in the MPEG-2 standard. A typical block diagram of a video MPEG-2 coder is depicted in FIG. 1. Such a system includes the following functional blocks:
1) Chroma Filter Block from 4:2:2 to 4:2:0
In this block there is a low pass finite time response filter operating on the chrominance component, which allows the substitution of any pixel with the weighed sum of neighboring pixels placed on the same column and multiplied by appropriate coefficients. This allows a subsequent subsampling by two, thus obtaining a halved vertical definition of the chrominance.
2) Frame Ordinator
This blocks includes one or several frame memories outputting the frames in the coding order required by the MPEG standard. For example, if the input sequence is I B B P B B P etc., the output order will be I P B B P B B . . . .
I (Intra coded picture) is a frame or a half-frame containing temporal redundance;
P (Predicted-picture) is a frame or a half-frame whose temporal redundance in respect to the preceding I or P (previously co/decoded) has been removed;
B (Bidirectionally predicted-picture) is a frame or a half-frame whose temporal redundance with respect to the preceding I and subsequent P (or preceding P and subsequent P, or preceding P and subsequent I) has been removed (in both cases the I and P pictures must be considered as already co/decoded).
Each frame buffer in the format 4:2:0 occupies the following memory amount:
Standard PAL
xe2x80x83720xc3x97576xc3x978 for the luminance (Y)=3,317,760 bits
360xc3x97288xc3x978 for the chrominance (U)=829,440 bits
360xc3x97288xc3x978 for the chrominance (V)=829,440 bits
total Y+U+V=4,976,640 bits
Standard NTSC
720xc3x97480xc3x978 for the luminance (Y)=2,764,800 bits
360xc3x97240xc3x978 for the chrominance (U)=691,200 bits
360xc3x97240xc3x978 for the chrominance (V)=691,200 bits
total Y+U+V=4,147,200 bits 
3) Estimator
This block is able to remove the temporal redundance from the P and B pictures.
4) DCT
This is the block that implements the discrete cosine transform according to the MPEG-2 standard. The I picture and the error pictures P and B are divided in blocks of 8*8 pixels Y, U, V, on which the DCT transform is performed.
5) Quantizer Q
An 8*8 block resulting from the DCT transform is then divided by a so-called quantizing matrix (in particular to divide the cosine transformed matrix of the macroblock by the matrix mQuant*Quantizer_Matrix where Quantizer_Matrix is a priori established and can vary from picture to picture) to reduce more or less drastically the bit number magnitude of the DCT coefficients. In such case, the information associated to the highest frequencies, less visible to human sight, tends to be removed. The result is reordered and sent to the subsequent block.
6) Variable Length Coding (VLC)
The codification words output from the quantizer tend to contain null coefficients in a more or less large number, followed by nonnull values. The null values preceding the first nonnull value are counted and the count figure constitutes the first portion of a codification word, the second portion of which represents the nonnull coefficient.
These pairs tend to assume values more probable than others. The most probable ones are coded with relatively short words (composed of 2, 3 or 4 bits) while the least probable are coded with longer words. Statistically, the number of output bits is less than when such a criterion is not implemented.
7) Multiplexer and Buffer
Data generated by the variable length coder for each macroblock, the motion vectors, the kind of macroblock I/P/B, the mQuant values, the quantizing matrices of each picture and other syntactic elements are assembled for constructing the serial bitstream whose final syntax is fully defined by the MPEG-2 video section standard. The resulting bitstream is stored in a memory buffer, the limit size of which is defined by the MPEG-2 standard requisite that the buffer cannot be overflown, otherwise a loss of information useful in decoding would occur. The quantizer block Q attends to the respect of such a limit, by making more or less drastic the division of the DCT 8*8 blocks depending on how far the system is from the filling or depletion limit of such a memory buffer and on the energy of the luminance component of the 16*16 source macroblock taken upstream of the motion estimation, of the prediction error generation and DCT transform processes.
8) Inverse Variable Length Coding (I-VLC)
The variable length coding functions specified above are executed in the inverse order.
9) Inverse Quantization (IQ)
The words output by the I-VLC block are reordered in the 8*8 block structure, which is multiplied by the same quantizing matrix used for its previous quantization.
10) Inverse DCT (I-DCT)
The DCT transform function is inverted and applied to the 8*8 block output by the inverse quantization process. This permits a pass from the domain of spatial frequencies to the pixel domain.
11) Motion Compensation and Storage
At the output of the I-DCT, either of the following may be present:
a decoded I picture (or half-picture) which must be stored in a respective frame memory for removing subsequently the temporal redundance in respect thereto from successive P and B pictures; or
a decoded prediction error picture (or half-picture) P or B which must be summed to the information previously removed during the motion estimation phase. In case of a P picture, such a resulting sum, stored in dedicated frame memory is used during the motion estimation process for the successive P pictures and B pictures.
These frame memories are distinct from the memories used for re-arranging the blocks.
12) Display Unit from 4:2:0 to 4:2:2
This unit converts the pictures from the format 4:2:0 to the format 4:2:2 and generates the interlaced format for the subsequent displaying. The chrominance components eliminated via the functional block 1, are restored by interpolation of the neighboring pixels. The interpolation includes a weighed sum of the neighboring pixels for appropriate coefficients and in limiting between 0 and 255 the value so obtained.
Let us consider a picture frame formed by a pair of half-frames. Each half-frame is formed by luminance and chrominance components. Let us suppose, for example, to apply the algorithm for measuring the macroblock activity only on the most energetic component, that is the richest of information, such as the luminance component.
Let this component be represented in form of a matrix of N rows and M columns. Let us divide each frame in portions called macroblocks, each of R rows and S columns. The results of the divisions N/R and M/S must be two integers, not necessarily equals to each other.
The MPEG2 establishes the dimension R=16 and S=16 which are considered as a good example for illustrating the method of the present invention.
Let MBq(i,j) be a macroblock belonging to the current frame and subjected to MPEG2 coding (motion estimation, prediction error calculation, DCT transform, quantization etc.) and whose first pixel, at the top left side, is in the cross-position between the i-th row and j-th column. The pair (i,j) is characterized in that i and j are integer multiples of R and S, respectively.
The location of such a macroblock on the picture and the dashed horizontal arrows indicating the scanning order used to locate macroblocks, are depicted in FIG. 5.
Let MBe(i,j) be the prediction error macroblock calculated as the difference between corresponding pixels of two macroblocks: the first being the MBq(i,j) macroblock belonging to the current frame and the second being a macroblock MBp(k,h) that resulted to be the best predictor of MBq at the end of the process of motion estimation and belonging to a precedent and/or to a following frame or being an average of both. In particular, if the current picture is of I kind then MBe(i,j)=MBq(i,j), while if the picture is of P or B kind then MBq(i,j)=MBq(i,j)xe2x88x92MBp(k,h).
As described in prior European Patent Applications EP-A-0917363 and EP-A-0944245, the motion estimation algorithm may include two steps: a first step, called xe2x80x9cCoarse searchxe2x80x9d and a second step called xe2x80x9cFine searchxe2x80x9d. The scheme of FIG. 2 is valid in case two pictures (Bidirectional Predictive) are present between two successive reference (I) pictures.
The first step of motion estimation is carried out directly on the original pictures, in their sequential order of sequence acquisition, generating a succession of motion fields (xe2x80x9cmotion vector fieldsxe2x80x9d) that will be used and refined during the second step of xe2x80x9cFine searchxe2x80x9d, by referring to previously encoded-decoded reference pictures (of I or P kind) according to the encoding order that is necessarily different from the order of the pictures.
Unlike a common full-search motion estimation approach, in which all macroblocks contained in a certain area, called xe2x80x9csearch windowxe2x80x9d, of the picture are tested, in the approach described in the two above identified prior patent applications there is not the algorithmic need of establishing a priori the dimensions of such areas. Nevertheless, to make easier a correct alignment of vectors resulting from the two estimation steps and not waste bits, it is more convenient to determine in advance search windows that are the smallest possible ones, compatible with the motion content of the sequences to process.
There is also a second reason, due to the standard MPEG2 that makes necessary such search windows as described in paragraphs 6.2.3.1, 6.3.10,7.6.3.1 and 7.6.3.2 relating to the standard ISO/IEC 13818.2 in the section relating to the xe2x80x9cPicture coding extensionxe2x80x9d, in the produced bit-streams it is necessary to insert the so-called xe2x80x9cf-codexe2x80x9d or codes that the decoder will use to decode the encoded motion vectors. Such codes represents variability fields for the motion vectors (see table 7-8 of the standard), and this implicitly describes the maximum size of the search window applicable to the motion estimation of the encoder. They can be different for each picture, but they must be placed in the output stream before the data relative to the pixels that compose the picture.
It is evident the need for an adaptive and predictive algorithm, that establishes certain not excessively large search windows for each picture, to reduce the disalignment of the motion vectors and to save information bits, but also to avoid that search windows that are too small for the motion content of the sequences interfere negatively with the motion estimation process, impeding its correct detection.
It is an object of this invention to provide a method of estimating the motion field of a sequence of digital pictures that allows the setting of the optimal dimensions of a search window and the optimal length of the string used to encode motion vectors.
More precisely, an object of the invention is a method of estimating the motion field of a digital picture sequence that comprises subdividing a current picture to examine in an integer number of macroblocks, for each macroblock of the current picture determining a search window centered on a macroblock of a preceding picture placed in the same position of the considered macroblock of the current picture, carrying out a motion estimation between the considered macroblock of the current picture and the macroblock most similar to it included in the window. The method of the invention is characterized in that at least a dimension of the search window is established in function of the corresponding dimension of the search window used for the preceding picture, of the estimated motion field of the preceding picture and of certain arbitrary threshold values.
A preferred way of calculating the considered dimension of the search window established for the current picture includes setting it equal to the corresponding dimension of the search window used for the preceding picture if the maximum motion vector of the preceding picture is comprised between a pair of threshold values upper and lower, or setting it equal to one half of the corresponding search window used for the preceding picture, if the maximum motion vector of the preceding picture is lower than the lower threshold, or setting it equal to the double of the corresponding dimension of the search window used for the preceding picture, if the maximum motion vector of the preceding picture is greater than the upper threshold.
The method of the invention may include a preliminary motion estimation step, carried out in the above described way, followed by a fine estimation step wherein at least a dimension of the search window is established as a function of the corresponding dimension of the search window used for the preceding picture, of motion vectors of the preceding and current pictures, of lengths of bit-strings used to encode the motion vectors, of the kind of the current picture and of a certain arbitrary threshold.